Termination w.r.t. Q of the following Term Rewriting System could not be shown:
Q restricted rewrite system:
The TRS R consists of the following rules:
__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isList → U11(isPalListKind)
isList → tt
isList → U21(isPalListKind)
isNeList → U31(isPalListKind)
isNeList → U41(isPalListKind)
isNeList → U51(isPalListKind)
isNePal → U61(isPalListKind)
isNePal → U71(isQid)
isPal → U81(isPalListKind)
isPal → tt
isPalListKind → tt
isPalListKind → U91(isPalListKind)
isQid → tt
Q is empty.
↳ QTRS
↳ DependencyPairsProof
Q restricted rewrite system:
The TRS R consists of the following rules:
__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isList → U11(isPalListKind)
isList → tt
isList → U21(isPalListKind)
isNeList → U31(isPalListKind)
isNeList → U41(isPalListKind)
isNeList → U51(isPalListKind)
isNePal → U61(isPalListKind)
isNePal → U71(isQid)
isPal → U81(isPalListKind)
isPal → tt
isPalListKind → tt
isPalListKind → U91(isPalListKind)
isQid → tt
Q is empty.
Using Dependency Pairs [1,15] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:
U511(tt) → ISPALLISTKIND
U551(tt) → ISLIST
U521(tt) → ISPALLISTKIND
U621(tt) → ISQID
U221(tt) → ISPALLISTKIND
U621(tt) → U631(isQid)
U311(tt) → U321(isPalListKind)
U511(tt) → U521(isPalListKind)
ISLIST → ISPALLISTKIND
U441(tt) → U451(isList)
U431(tt) → U441(isPalListKind)
U421(tt) → U431(isPalListKind)
U311(tt) → ISPALLISTKIND
__1(__(X, Y), Z) → __1(Y, Z)
U221(tt) → U231(isPalListKind)
U421(tt) → ISPALLISTKIND
U541(tt) → ISNELIST
ISPAL → ISPALLISTKIND
U111(tt) → U121(isPalListKind)
U441(tt) → ISLIST
ISNEPAL → U711(isQid)
U251(tt) → ISLIST
U731(tt) → U741(isPalListKind)
U231(tt) → ISPALLISTKIND
ISNELIST → ISPALLISTKIND
U731(tt) → ISPALLISTKIND
U551(tt) → U561(isList)
U451(tt) → ISNELIST
U541(tt) → U551(isNeList)
U241(tt) → ISLIST
U821(tt) → ISNEPAL
U721(tt) → U731(isPal)
U821(tt) → U831(isNePal)
__1(__(X, Y), Z) → __1(X, __(Y, Z))
U241(tt) → U251(isList)
U531(tt) → ISPALLISTKIND
U611(tt) → U621(isPalListKind)
ISNEPAL → ISPALLISTKIND
U451(tt) → U461(isNeList)
U811(tt) → ISPALLISTKIND
U321(tt) → U331(isQid)
U411(tt) → U421(isPalListKind)
ISPAL → U811(isPalListKind)
U711(tt) → U721(isPalListKind)
U121(tt) → U131(isNeList)
U611(tt) → ISPALLISTKIND
ISLIST → U111(isPalListKind)
U721(tt) → ISPAL
U111(tt) → ISPALLISTKIND
U211(tt) → U221(isPalListKind)
U911(tt) → ISPALLISTKIND
U711(tt) → ISPALLISTKIND
ISNEPAL → ISQID
U411(tt) → ISPALLISTKIND
U811(tt) → U821(isPalListKind)
ISPALLISTKIND → ISPALLISTKIND
U231(tt) → U241(isPalListKind)
ISNEPAL → U611(isPalListKind)
ISNELIST → U511(isPalListKind)
ISNELIST → U311(isPalListKind)
U531(tt) → U541(isPalListKind)
U321(tt) → ISQID
U251(tt) → U261(isList)
U121(tt) → ISNELIST
ISPALLISTKIND → U911(isPalListKind)
U521(tt) → U531(isPalListKind)
U911(tt) → U921(isPalListKind)
ISNELIST → U411(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → ISPALLISTKIND
U431(tt) → ISPALLISTKIND
The TRS R consists of the following rules:
__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isList → U11(isPalListKind)
isList → tt
isList → U21(isPalListKind)
isNeList → U31(isPalListKind)
isNeList → U41(isPalListKind)
isNeList → U51(isPalListKind)
isNePal → U61(isPalListKind)
isNePal → U71(isQid)
isPal → U81(isPalListKind)
isPal → tt
isPalListKind → tt
isPalListKind → U91(isPalListKind)
isQid → tt
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
Q DP problem:
The TRS P consists of the following rules:
U511(tt) → ISPALLISTKIND
U551(tt) → ISLIST
U521(tt) → ISPALLISTKIND
U621(tt) → ISQID
U221(tt) → ISPALLISTKIND
U621(tt) → U631(isQid)
U311(tt) → U321(isPalListKind)
U511(tt) → U521(isPalListKind)
ISLIST → ISPALLISTKIND
U441(tt) → U451(isList)
U431(tt) → U441(isPalListKind)
U421(tt) → U431(isPalListKind)
U311(tt) → ISPALLISTKIND
__1(__(X, Y), Z) → __1(Y, Z)
U221(tt) → U231(isPalListKind)
U421(tt) → ISPALLISTKIND
U541(tt) → ISNELIST
ISPAL → ISPALLISTKIND
U111(tt) → U121(isPalListKind)
U441(tt) → ISLIST
ISNEPAL → U711(isQid)
U251(tt) → ISLIST
U731(tt) → U741(isPalListKind)
U231(tt) → ISPALLISTKIND
ISNELIST → ISPALLISTKIND
U731(tt) → ISPALLISTKIND
U551(tt) → U561(isList)
U451(tt) → ISNELIST
U541(tt) → U551(isNeList)
U241(tt) → ISLIST
U821(tt) → ISNEPAL
U721(tt) → U731(isPal)
U821(tt) → U831(isNePal)
__1(__(X, Y), Z) → __1(X, __(Y, Z))
U241(tt) → U251(isList)
U531(tt) → ISPALLISTKIND
U611(tt) → U621(isPalListKind)
ISNEPAL → ISPALLISTKIND
U451(tt) → U461(isNeList)
U811(tt) → ISPALLISTKIND
U321(tt) → U331(isQid)
U411(tt) → U421(isPalListKind)
ISPAL → U811(isPalListKind)
U711(tt) → U721(isPalListKind)
U121(tt) → U131(isNeList)
U611(tt) → ISPALLISTKIND
ISLIST → U111(isPalListKind)
U721(tt) → ISPAL
U111(tt) → ISPALLISTKIND
U211(tt) → U221(isPalListKind)
U911(tt) → ISPALLISTKIND
U711(tt) → ISPALLISTKIND
ISNEPAL → ISQID
U411(tt) → ISPALLISTKIND
U811(tt) → U821(isPalListKind)
ISPALLISTKIND → ISPALLISTKIND
U231(tt) → U241(isPalListKind)
ISNEPAL → U611(isPalListKind)
ISNELIST → U511(isPalListKind)
ISNELIST → U311(isPalListKind)
U531(tt) → U541(isPalListKind)
U321(tt) → ISQID
U251(tt) → U261(isList)
U121(tt) → ISNELIST
ISPALLISTKIND → U911(isPalListKind)
U521(tt) → U531(isPalListKind)
U911(tt) → U921(isPalListKind)
ISNELIST → U411(isPalListKind)
ISLIST → U211(isPalListKind)
U211(tt) → ISPALLISTKIND
U431(tt) → ISPALLISTKIND
The TRS R consists of the following rules:
__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isList → U11(isPalListKind)
isList → tt
isList → U21(isPalListKind)
isNeList → U31(isPalListKind)
isNeList → U41(isPalListKind)
isNeList → U51(isPalListKind)
isNePal → U61(isPalListKind)
isNePal → U71(isQid)
isPal → U81(isPalListKind)
isPal → tt
isPalListKind → tt
isPalListKind → U91(isPalListKind)
isQid → tt
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 4 SCCs with 36 less nodes.
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
ISPALLISTKIND → U911(isPalListKind)
ISPALLISTKIND → ISPALLISTKIND
U911(tt) → ISPALLISTKIND
The TRS R consists of the following rules:
__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isList → U11(isPalListKind)
isList → tt
isList → U21(isPalListKind)
isNeList → U31(isPalListKind)
isNeList → U41(isPalListKind)
isNeList → U51(isPalListKind)
isNePal → U61(isPalListKind)
isNePal → U71(isQid)
isPal → U81(isPalListKind)
isPal → tt
isPalListKind → tt
isPalListKind → U91(isPalListKind)
isQid → tt
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
U821(tt) → ISNEPAL
U711(tt) → U721(isPalListKind)
U811(tt) → U821(isPalListKind)
U721(tt) → ISPAL
ISPAL → U811(isPalListKind)
ISNEPAL → U711(isQid)
The TRS R consists of the following rules:
__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isList → U11(isPalListKind)
isList → tt
isList → U21(isPalListKind)
isNeList → U31(isPalListKind)
isNeList → U41(isPalListKind)
isNeList → U51(isPalListKind)
isNePal → U61(isPalListKind)
isNePal → U71(isQid)
isPal → U81(isPalListKind)
isPal → tt
isPalListKind → tt
isPalListKind → U91(isPalListKind)
isQid → tt
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
U221(tt) → U231(isPalListKind)
U241(tt) → U251(isList)
U541(tt) → ISNELIST
U551(tt) → ISLIST
U231(tt) → U241(isPalListKind)
U111(tt) → U121(isPalListKind)
U441(tt) → ISLIST
U411(tt) → U421(isPalListKind)
ISNELIST → U511(isPalListKind)
U531(tt) → U541(isPalListKind)
U251(tt) → ISLIST
U511(tt) → U521(isPalListKind)
U121(tt) → ISNELIST
U441(tt) → U451(isList)
U451(tt) → ISNELIST
U521(tt) → U531(isPalListKind)
ISLIST → U111(isPalListKind)
ISNELIST → U411(isPalListKind)
U541(tt) → U551(isNeList)
U241(tt) → ISLIST
U211(tt) → U221(isPalListKind)
U431(tt) → U441(isPalListKind)
ISLIST → U211(isPalListKind)
U421(tt) → U431(isPalListKind)
The TRS R consists of the following rules:
__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isList → U11(isPalListKind)
isList → tt
isList → U21(isPalListKind)
isNeList → U31(isPalListKind)
isNeList → U41(isPalListKind)
isNeList → U51(isPalListKind)
isNePal → U61(isPalListKind)
isNePal → U71(isQid)
isPal → U81(isPalListKind)
isPal → tt
isPalListKind → tt
isPalListKind → U91(isPalListKind)
isQid → tt
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
↳ QTRS
↳ DependencyPairsProof
↳ QDP
↳ DependencyGraphProof
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDP
Q DP problem:
The TRS P consists of the following rules:
__1(__(X, Y), Z) → __1(Y, Z)
__1(__(X, Y), Z) → __1(X, __(Y, Z))
The TRS R consists of the following rules:
__(__(X, Y), Z) → __(X, __(Y, Z))
__(X, nil) → X
__(nil, X) → X
U11(tt) → U12(isPalListKind)
U12(tt) → U13(isNeList)
U13(tt) → tt
U21(tt) → U22(isPalListKind)
U22(tt) → U23(isPalListKind)
U23(tt) → U24(isPalListKind)
U24(tt) → U25(isList)
U25(tt) → U26(isList)
U26(tt) → tt
U31(tt) → U32(isPalListKind)
U32(tt) → U33(isQid)
U33(tt) → tt
U41(tt) → U42(isPalListKind)
U42(tt) → U43(isPalListKind)
U43(tt) → U44(isPalListKind)
U44(tt) → U45(isList)
U45(tt) → U46(isNeList)
U46(tt) → tt
U51(tt) → U52(isPalListKind)
U52(tt) → U53(isPalListKind)
U53(tt) → U54(isPalListKind)
U54(tt) → U55(isNeList)
U55(tt) → U56(isList)
U56(tt) → tt
U61(tt) → U62(isPalListKind)
U62(tt) → U63(isQid)
U63(tt) → tt
U71(tt) → U72(isPalListKind)
U72(tt) → U73(isPal)
U73(tt) → U74(isPalListKind)
U74(tt) → tt
U81(tt) → U82(isPalListKind)
U82(tt) → U83(isNePal)
U83(tt) → tt
U91(tt) → U92(isPalListKind)
U92(tt) → tt
isList → U11(isPalListKind)
isList → tt
isList → U21(isPalListKind)
isNeList → U31(isPalListKind)
isNeList → U41(isPalListKind)
isNeList → U51(isPalListKind)
isNePal → U61(isPalListKind)
isNePal → U71(isQid)
isPal → U81(isPalListKind)
isPal → tt
isPalListKind → tt
isPalListKind → U91(isPalListKind)
isQid → tt
Q is empty.
We have to consider all minimal (P,Q,R)-chains.